package com.ln.leetcode._2050;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    public int minimumTime(int n, int[][] relations, int[] time) {
        // 构建前驱节点组
        List<Integer>[] prev = new List[n + 1];
        // 初始化前驱节点信息
        for (int i = 0; i < prev.length; i++) {
            prev[i] = new ArrayList<>();
        }
        // 填充值
        for (int[] relation : relations) {
            prev[relation[1]].add(relation[0]);
        }

        int result = 0;
        Map<Integer, Integer> cache = new HashMap<>();

        // 遍历所有节点，取最大值
        for (int i = 1; i <= n; i++) {
            // 如果当前节点没有前驱，则为 time[i - 1]
            // 如果当前节点存在前驱，则取所有前驱节点中最大的一个值。 这个情况使用 DP 求解
            result = Math.max(result, dp(i, time, prev, cache));
        }

        return result;
    }

    private int dp(int i, int[] time, List<Integer>[] prev, Map<Integer, Integer> cache) {
        if (!cache.containsKey(i)) {
            int prevLen = 0;
            for (Integer prevIndex : prev[i]) {
                prevLen = Math.max(prevLen, dp(prevIndex, time, prev, cache));
            }
            // 加上自己的时间
            prevLen += time[i - 1];
            cache.put(i, prevLen);
        }
        return cache.get(i);
    }

    @Test
    public void test() {
        Assert.assertEquals(8, minimumTime(3, new int[][]{{1, 3}, {2, 3}}, new int[]{3, 2, 5}));
        Assert.assertEquals(12, minimumTime(5, new int[][]{{1, 5}, {2, 5}, {3, 5}, {3, 4}, {4, 5}}, new int[]{1, 2, 3, 4, 5}));
    }

}
